﻿
namespace Leetcode.N1406;
public class Solution
{
    public string StoneGameIII(int[] stoneValue)
    {
        var ans = new (int sum, int count)[stoneValue.Length];
        var sums = new int[stoneValue.Length + 1];
        sums[0] = 0;
        for (int i = 1; i < sums.Length; i++)
        {
            sums[i] = sums[i - 1] + stoneValue[i - 1];
        }

        const int PickCount = 3;

        for (int i = stoneValue.Length - 1; i >= 0; i--)
        {
            (int sum, int count) r = (int.MinValue, 0);
            for (int k = 0; k < PickCount && i + k < ans.Length; k++)
            {
                var nextIndex = i + 1 + k;
                var sum1 = sums[nextIndex] - sums[i];
                var sum2 = 0;

                if (nextIndex < ans.Length)
                {
                    var next = ans[nextIndex];
                    if (nextIndex + next.count < ans.Length)
                    {
                        var next2 = ans[nextIndex + next.count];
                        sum2 = next2.sum;
                    }
                }

                if (sum1 + sum2 >= r.sum)
                {
                    r = (sum1 + sum2, k + 1);
                }
            }
            ans[i] = r;
        }

        var aliceSum = ans[0].sum;
        var bobSum = ans[0].count < ans.Length ? ans[ans[0].count].sum : 0;
        if (aliceSum > bobSum)
        {
            return "Alice";
        }
        else if (aliceSum < bobSum)
        {
            return "Bob";
        }
        else
        {
            return "Tie";
        }
    }
}